package com.su.test;

import java.util.Arrays;

public class DFS extends Strategy{
    public DFS() {
    }

    @Override
    public void run() {
        super.steps = 0;
        super.lastNode = null;

        int emptyIndex=0;     //记录空格的位置
        for (int i = 0; i < length; i++) {
            if(initArr[i] == 0){
                emptyIndex = i;
                break;
            }
        }
        Node initNode = new Node(initArr,emptyIndex,null,0);
        backTrack(initNode);
    }

    private void backTrack(Node curNode){
        if (curNode.depth >= 21 || super.lastNode != null){     //终止条件
            return;
        }
        super.steps++;
        if(Arrays.equals(curNode.num, targetArr)){
            super.lastNode = curNode;
            return;
        }


        int emptyIndexOfCur = curNode.emptyIndex;   //当前节点空格位置
        int lastEmptyIndex = curNode.parent != null ? curNode.parent.emptyIndex : -1;

        //左移
        if(emptyIndexOfCur % this.col > 0 && emptyIndexOfCur - 1 != lastEmptyIndex){
            int nextArr[] = move(curNode.num,emptyIndexOfCur,-1);
            Node nextNode = new Node(nextArr,emptyIndexOfCur-1, curNode,curNode.depth + 1);
            backTrack(nextNode);
        }
        //上移
        if(emptyIndexOfCur > this.col  && emptyIndexOfCur - this.col != lastEmptyIndex){
            int nextArr[] = move(curNode.num,emptyIndexOfCur,-this.col);
            Node nextNode = new Node(nextArr,emptyIndexOfCur-this.col, curNode,curNode.depth + 1);
            backTrack(nextNode);
        }
        //右移
        if(emptyIndexOfCur % this.col < this.col - 1  && emptyIndexOfCur + 1 != lastEmptyIndex){
            int nextArr[] = move(curNode.num,emptyIndexOfCur,1);
            Node nextNode = new Node(nextArr,emptyIndexOfCur + 1, curNode,curNode.depth + 1);
            backTrack(nextNode);
        }
        //下移
        if (emptyIndexOfCur < length - this.col && emptyIndexOfCur + this.col != lastEmptyIndex){
            int nextArr[] = move(curNode.num,emptyIndexOfCur,this.col);
            Node nextNode = new Node(nextArr,emptyIndexOfCur + this.col, curNode,curNode.depth + 1);
            backTrack(nextNode);
        }
    }
}
/*
输入初始数组、目标数组
根据初始数组构建初始节点

Start: if(当前节点n的深度大于dmax ||
        已经找到目标节点)
            结束
       if(当前节点n == 目标节点){
            创建一个List,用来保存最佳路线的数组（表示八数码）
            while(节点n != NULL){
                将节点n的数组添加至List
                节点n = 节点n->parent
            }
            倒序输出List
       }
       for(当前节点n的每一个子节点X){
         子节点X深度 = 当前节点深度 + 1
         递归回到Start,判断子节点X
     }


 */
